还没有笔记
选中页面文字后点击「高亮」按钮添加
循环群的故事与初等数论（因式分解、素数、同余）密切相关。我们使用一些关于$\mathbb{N}$中加法、乘法和序的结果，从“第一原理”证明了一些基本事实。其中最基本的事实之一如下：
设$n \in \mathbb{N}$。则对于所有的$a \in \mathbb{Z}$，存在唯一的整数$q$和$r$使得$0 \leq r \leq n-1$并且$a=n q+r$。
这里$q$代表商，$r$代表余数。
证明。存在性：定义$\mathbb{Z}$的子集$X$为
首先我们声称$X \neq \emptyset$。如果$a \geq 0$，取$q=0$，则$a-n q=a \geq 0$是$X$的一个元素。如果$a<0$，取$q=a=-k$，例如，$k>0$。则$a-n q=-k+n k=k(n-1) \geq 0$因为$k>0$且$n-1 \geq 0$。则$a-n a \in X$，因此$X \neq \emptyset$。
接下来我们声称$X$有一个最小元素。如果$0 \in X$，那么$0$显然是$X$的最小元素。如果$0 \notin X$，那么$X \subseteq \mathbb{N}$，因此，由于$X \neq \emptyset$，根据良序原理，$X$有一个最小元素。在任何情况下，设$r$是$X$的最小元素。那么根据定义，$r=a-n q$且$r \geq 0$。注意$a=n q+r$。为了证明定理的存在性部分，只需证明$r \leq n-1$。我们通过反证法论证：如果$r \geq n$，那么$0 \leq r-n<r$。但是
由于$r-n \geq 0$，根据$X$的定义，$r-n \in X$。但是$r-n<r$，这与选择$r$作为$X$的最小元素相矛盾。因此$r \leq n-1$且$a=n q+r$。
唯一性：假设$a=n q_{1}+r_{1}=n q_{2}+r_{2}$，其中$q_{i}, r_{i} \in \mathbb{Z}$且$0 \leq r_{i} \leq n-1$，对于$i=1,2$。我们必须证明$q_{1}=q_{2}$且$r_{1}=r_{2}$。现在$r_{1} \leq r_{2}$或$r_{2} \leq r_{1}$。通过对称性，我们可以假设$r_{1} \leq r_{2}$。那么
此外，
如果$r_{2}-r_{1} \neq 0$，那么$r_{2}-r_{1}$是一个可被$n$整除的正整数，因此$r_{2}-r_{1} \geq n$。这与$r_{2}-r_{1} \leq n-1$相矛盾。因此$r_{2}-r_{1}=0$，即$r_{2}=r_{1}$。那么$n\left(q_{1}-q_{2}\right)=0$。由于$n \in \mathbb{N}, n \neq 0$。因此$q_{1}-q_{2}=0$，所以$q_{1}=q_{2}$。
设$n \in \mathbb{N}$。$\mathbb{Z} / n \mathbb{Z}$中的每个同余类$[a]_{n}$都有一个唯一的代表$r$，$0 \leq r \leq n-1$。因此$\#(\mathbb{Z} / n \mathbb{Z})=n$，作为一个集合，
证明。给定$[a]_{n} \in \mathbb{Z} / n \mathbb{Z}$，写$a=n q+r$，其中$0 \leq r \leq n-1$。那么$a \equiv r \bmod n$，所以$[a]_{n}=[r]_{n}$。为了说明$r$是$[a]_{n}$的唯一代表，使得$0 \leq r \leq n-1$，假设$\left[r_{1}\right]_{n}=\left[r_{2}\right]_{n}$，其中$0 \leq r_{1}, r_{2} \leq n-1$。那么$a=n q_{1}+r_{1}=n q_{2}+r_{2}$，对于某些整数$q_{1}, q_{2}$，因此根据定理 1.1.1的唯一性陈述，$r_{1}=r_{2}$。
设$G$是一个群，设$g \in G$是一个（有限）阶为$n$的元素。那么，对于所有的$N \in \mathbb{Z}$, $g^{N}=1 \Longleftrightarrow n \mid N$。
证明。设$N \in \mathbb{Z}$是任意的。那么$N=n q+r$，其中$0 \leq r \leq n-1$，并且$n \mid N \Longleftrightarrow r=0$，并且
此外，根据阶的定义，$0 \leq r \leq n-1$，则$g^{r} \neq 1$。因此，对于$0 \leq r \leq n-1, g^{r}=1 \Longleftrightarrow r=0$。因此$g^{N}=1 \Longleftrightarrow n \mid N$。
我们已经看到，推论 1.1.3意味着，如果$g \in G$的阶为$n$，那么$\langle g\rangle \cong \mathbb{Z} / n \mathbb{Z}$。事实上，存在一个唯一的同构$f: \mathbb{Z} / n \mathbb{Z} \rightarrow\langle g\rangle$使得$f\left([1]_{n}\right)=g$。此外，$\langle g\rangle$的每个元素都可以唯一地写成$g^{r}, 0 \leq r \leq n-1$。因此$\#(\langle g\rangle)=n$。
每个循环群都同构于$\mathbb{Z}$或$\mathbb{Z} / n \mathbb{Z}$。
证明。每个循环群$G$都形如$\langle g\rangle$，对于某个$g \in G$。证明然后遵循命题 3.2.4，如果$g$具有无限阶，并遵循上述（iii），如果$g$具有有限阶。
从现在开始，我们将专注于群$\mathbb{Z}$和$\mathbb{Z} / n \mathbb{Z}$。前面的推论告诉我们，任何对$\mathbb{Z}$或$\mathbb{Z} / n \mathbb{Z}$证明的代数结果（例如，关于子群性质或元素阶的结果）都将对任意循环群具有自然的类比。
$\mathbb{Z}$的每个子群都是循环的。
证明。设$H \leq \mathbb{Z}$。如果$H=\{0\}$，那么$H=\langle 0\rangle$，因此$H$是循环的。因此我们可以假设存在一个$a \in H, a \neq 0$。那么$-a \in H$，并且$a>0$或$-a>0$。特别是，集合$H \cap \mathbb{N}$是非空的。设$d$是$H \cap \mathbb{N}$的最小元素，根据良序原理它存在。为了证明命题，我们将证明$H=\langle d\rangle$。我们将通过证明$\langle d\rangle \subseteq H$和$H \subseteq\langle d\rangle$来做到这一点。
由于$d \in H \cap \mathbb{N}, d \in H$，因此$\langle d\rangle \subseteq H$。所以我们必须证明$H \subseteq\langle d\rangle$。设$a \in H$；我们必须证明$a \in\langle d\rangle$。对$a$应用带余数的长除法，我们可以写$a=d q+r$，其中$0 \leq r \leq d-1$。正如我们所见，$\langle d\rangle \subseteq H$，因此$d q=q \cdot d \in H$。由于$H$是一个子群，$-d q \in H$，并且，由于$a \in H, a-d q=r \in H$。如果$r>0$，那么$r \in \mathbb{N}, r \in H$，并且$r \leq d-1<d$。这与选择$d$作为$H$的最小正元素相矛盾。因此$r=0$，即$a-d q=0$，因此$a=d q \in\langle d\rangle$。由此可见$H \subseteq\langle d\rangle$，因此$H=\langle d\rangle$。因此$H$是循环的。
证明还表明，如果$H \leq \mathbb{Z}$不是平凡子群$\{0\}$，那么$H=\langle d\rangle \subseteq$本身是一个无限循环群。因此$H \cong \mathbb{Z}$，并且$H$的两个生成元是$\pm d$。
一个非常相似的论证表明：
设$n \in \mathbb{N}$。那么$\mathbb{Z} / n \mathbb{Z}$的每个子群$H$都是循环的。
证明。在这种情况下，我们设
那么$X$是一个有限集。如前所述，存在一个最小元素$d \in X$，因此$[d]_{n} \in H$。我们声称$H=\left\langle[d]_{n}\right\rangle$。显然$\left\langle[d]_{n}\right\rangle \subseteq H$。反之，如果$[k]_{n} \in H$，我们可以写$k=d q+s$，其中$0 \leq s \leq d-1$。那么$[k]_{n}=[d q+s]_{n}=q \cdot[d]_{n}+[s]_{n}$。由此可见$[s]_{n}=q \cdot[d]_{n}-[k]_{n} \in H$。由于$0 \leq s \leq d-1<d \leq n-1$，根据$d$的定义，我们必须有$s=0$。因此$[k]_{n} \in\left\langle[d]_{n}\right\rangle$。由此可见$H \subseteq\left\langle[d]_{n}\right\rangle$，因此$H=\left\langle[d]_{n}\right\rangle$。
这里，我们使用循环群都同构于$\mathbb{Z}$或$\mathbb{Z} / n \mathbb{Z}$的结果，以及练习 2.31中先前讨论的事实：如果$f: G_{1} \rightarrow G_{2}$是一个同构，那么$G_{1}$的子集$H$是$G_{1}$的子群$\Longleftrightarrow f(H)$是$G_{2}$的子群，并且（使用练习 2.19），如果$H=\langle g\rangle$是$G_{1}$的循环子群，那么$f(\langle g\rangle)$是$G_{2}$的循环子群，事实上它是$\langle f(g)\rangle$。因此，函数$H \mapsto f(H)$是从$G_{1}$的子群集合到$G_{2}$的子群集合的双射，此外在这种情况下，$H$和$f(H)$是同构的。特别是，$H$是循环的$\Longleftrightarrow f(H)$是循环的。
$\mathbb{Z}$的每个子群都可以唯一地描述为$\langle 0\rangle$或$\langle d\rangle$，其中$d>0$。我们将在后面给出$\mathbb{Z} / n \mathbb{Z}$的子群及其可能的生成元的类似精确描述。
回顾一下，如果$a, b \in \mathbb{Z}$，那么$a \mid b \Longleftrightarrow$存在一个$k \in \mathbb{Z}$使得$b=a k \Longleftrightarrow b$是$a$的倍数$\Longleftrightarrow b \in\langle a\rangle \Longleftrightarrow\langle b\rangle \subseteq\langle a\rangle$。我们有以下整除性的简单性质：
(1) 对于所有的$a \in \mathbb{Z}, a \mid a$。
(2) 整除性具有传递性：如果$a \mid b$且$b \mid c$，那么$a \mid c$。
(3) 如果$a \mid b$且$a \mid c$，那么，对于所有的$r, s \in \mathbb{Z}, a \mid(r b+s c)$。
(4) 对于所有的$a \in \mathbb{Z}, a \mid 0$，但$0 \mid a \Longleftrightarrow a=0$。
(5) 对于所有的$a \in \mathbb{Z}, 1 \mid a$，但$a \mid 1 \Longleftrightarrow a= \pm 1$。
(6) 对于所有的$a, b \in \mathbb{Z}$，如果$a \mid b$且$b \mid a$，那么$b= \pm a$。
设$a, b \in \mathbb{Z}$，不都为$0$。$a$和$b$的最大公约数（记作$\operatorname{gcd}(a, b)$）是一个自然数$d \in \mathbb{N}$，使得$d|a, d| b$，并且，对于所有的$e \in \mathbb{Z}$，如果$e \mid a$且$e \mid b$，那么$e \mid d$。（有时人们将最大公约数写成$(a, b)$，但这会引起混淆，因为它也表示有序对。）
如果$a$和$b$的最大公约数存在，那么它是唯一的。
证明。如果$d_{1}$和$d_{2}$是$a$和$b$的两个最大公约数，那么$d_{1} \mid d_{2}$且$d_{2} \mid d_{1}$。根据上述(6)，由于定义$d_{1}, d_{2} \in \mathbb{N}$，$d_{1}=d_{2}$。
(i) 如果$d$是$a$和$b$的最大公约数，根据定义，它也是同时整除$a$和$b$的最大的自然数。然而，$d$具有定义中更强的性质。
(ii) 从小学起，计算$\operatorname{gcd}(a, b)=d$的常用方法是将$a$和$b$因式分解成素数的幂乘积。那么$d$的素因数是同时整除$a$和$b$的素数，并且素数$p$在$d$的因式分解中出现的幂次如下给出：如果$p^{n_{1}}$是整除$a$的$p$的最大幂次，并且$p^{n_{2}}$是整除$b$的$p$的最大幂次，那么整除$d$的$p$的最大幂次是$p^{\min \left(n_{1}, n_{2}\right)}$。然而，有更高效的计算$\operatorname{gcd}(a, b)$的方法，它们不涉及将$a$和$b$因式分解为素数（这是一个计算上非常困难的问题）。
以下结果告诉我们最大公约数总是存在的：
设$a, b \in \mathbb{Z}$，不都为$0$。
(i) $a$和$b$的最大公约数存在，并且根据前面备注中的(i)，它必然是唯一的。
(ii) 如果$d$是$a$和$b$的最大公约数，那么存在$n, m \in \mathbb{Z}$使得$d=\operatorname{gcd}(a, b)=a n+b m$。
(iii) 对于所有的$c \in \mathbb{Z}$，存在$x, y \in \mathbb{Z}$使得$a x+b y=c \Longleftrightarrow d \mid c$。
证明。(i) 考虑集合
根据定义，如果$c \in \mathbb{Z}$，那么$c \in H \Longleftrightarrow$存在$x, y \in \mathbb{Z}$使得$a x+b y=c$。我们声称$H$是$\mathbb{Z}$的子群，包含$a$和$b$；事实上，它是如前定义的由$a$和$b$生成的子群$\langle a, b\rangle$（因为$a x+b y=x \cdot a+y \cdot b$）。我们将直接证明这一点：首先，$H$在$+$下封闭，因为给定$H$的两个元素$a x_{1}+b y_{1}, a x_{2}+b y_{2}$，
显然，$0=a \cdot 0+b \cdot 0 \in H$，并且如果$a x+b y \in H$，那么$-(a x+b y)=a(-x)+b(-y) \in H$。因此$H$是一个子群。此外，注意$a=a \cdot 1+b \cdot 0 \in H$和$b=a \cdot 0+b \cdot 1 \in H$。
由于$\mathbb{Z}$的每个子群都是循环的，存在一个$d \in \mathbb{Z}$使得$H=\langle d\rangle$。此外，$H \neq\{0\}$因为$a, b \in H$并且根据假设它们至少有一个不是零。因此我们可以假设$d>0$，即$d \in \mathbb{N}$。为了完成(i)的证明，只需证明$d$是$a$和$b$的最大公约数。由于$a \in H=\langle d\rangle, d \mid a$。同样，$d \mid b$。因此，$d$是$a$和$b$的公约数。最后，如果$e \mid a$且$e \mid b$，那么$e \mid a n+b m=d$。因此$d=\operatorname{gcd}(a, b)$。
(ii) 根据构造，对于(i)中$d=\operatorname{gcd}(a, b)$，我们看到$d \in H$，因此$d=a n+b m$对于某些$n, m \in \mathbb{Z}$。
(iii) 所有形如$a x+b y$的整数$c$的集合根据定义是(i)的证明中的子群$H$。那里的论证表明$H=\langle d\rangle$是$d$的所有倍数的集合。将这两个事实结合起来，$c=a x+b y$对于某些$x, y \in \mathbb{Z} \Longleftrightarrow c \in\langle d\rangle \Longleftrightarrow d \mid c$。
在单独一节中，我们将描述一种高效的计算过程，即欧几里得算法，用于找到两个整数$a, b$（不都为$0$）的最大公约数$d$，并以$a n+b m$的形式写出$d$，其中$n, m \in \mathbb{Z}$。
(i) 的证明中使用的论证表明：如果$G$是阿贝尔群，并且群运算表示为$+$，并且$g_{1}, \ldots, g_{k} \in G$，那么集合
是$G$的一个子群，包含$g_{1}, \ldots, g_{k}$（事实上它是最小的此类子群）。
设$a, b \in \mathbb{Z}$，不都为$0$。如果$\operatorname{gcd}(a, b)=1$，那么$a$和$b$是互素的。换句话说，如果一个整数$e$同时整除$a$和$b$，那么$e$整除$1$，或者等价地$e= \pm 1$。
给定整数$a$和$b$，不都为$0$， $a$和$b$互素$\Longleftrightarrow$存在$x, y \in \mathbb{Z}$使得$a x+b y=1$。
证明。根据前面的推论，存在$x, y \in \mathbb{Z}$使得$a x+b y=1 \Longleftrightarrow d=\operatorname{gcd}(a, b)$整除$1 \Longleftrightarrow d=1$。
然后我们有以下基本结果：
设$a, b \in \mathbb{Z}$互素。如果$a \mid b c$，那么$a \mid c$。
证明。根据前面的推论，存在$x, y \in \mathbb{Z}$使得$a x+b y=1$。那么$c= c(a x)+c(b y)=a(c x)+(b c) y$。根据假设，$a \mid b c$并且显然$a \mid a$。因此$a \mid(a(c x)+(b c) y)=c$。
该推论最常应用于素数：
设$p \in \mathbb{N}$。如果$p>1$，并且对于所有的$n \in \mathbb{N}$，如果$n \mid p$那么$n=1$或$n=p$，则$p$是素数或质数。
然后我们有素数的以下性质：
设$p$是素数且$n \in \mathbb{Z}$。那么$p$和$n$要么互素，要么$p \mid n$。
证明。设$d=\operatorname{gcd}(p, n)$。那么$d \in \mathbb{N}$且$d \mid p$。因此，$d=1$或$d=p$。如果$d=1$，那么根据定义，$p$和$n$互素。如果$d=p$，那么$p \mid n$。
设$p$是素数且$a, b \in \mathbb{Z}$。如果$p \mid a b$，那么$p \mid a$或$p \mid b$。换句话说，如果素数整除乘积，那么它整除其中一个因子。
证明。假设$p$不整除$a$。那么，根据引理 1.2.10，$p$和$a$互素。那么，根据命题 1.2.8，$p$整除$b$。
设$p$是素数且$a_{1}, \ldots, a_{k} \in \mathbb{Z}$。如果$p \mid a_{1} \cdots a_{k}$，那么存在一个$i$使得$p \mid a_{i}$。
证明。这由上述内容和直观归纳论证得出。
前面的推论是以下定理的关键步骤之一：
设$n \in \mathbb{N}, n>1$。那么$n$可以唯一地因式分解为素数。更准确地说，存在素数$p_{1}, \ldots, p_{r}$使得$n=p_{1} \cdots p_{r}$，并且这个乘积是唯一的，其含义是，如果
其中$p_{i}$和$q_{j}$是素数，那么$r=s$，并且，在可能重新排序之后，$q_{i}=p_{i}$对于每个$i$。
证明。存在性：我们已经通过对$n$的完全归纳法证明了这一点。
唯一性：假设$p_{1} \cdots p_{r}=q_{1} \cdots q_{s}$，其中$p_{i}$和$q_{j}$是素数。我们通过对$r$的归纳法论证。如果$r=1$，那么$p_{1}=q_{1} \cdots q_{s}$，其中$q_{j}$是素数。因此$s=1$，否则$p_{1}$将具有非平凡因式分解，然后$p_{1}=q_{1}$。对于归纳步骤，假设我们已经对$r-1$证明了定理。设$p_{1} \cdots p_{r}=q_{1} \cdots q_{s}$。那么左侧是$p_{r}$的倍数，所以$p_{r}$整除$q_{1} \cdots q_{s}$。因此，存在一个$i$使得$p_{r} \mid q_{i}$。由于$q_{i}$是素数，$p_{r}=q_{i}$。在重新标记$q_{i}$之后，我们可以假设$i=s$。那么
所以在消去最后一个因子后，我们有$p_{1} \cdots p_{r-1}=q_{1} \cdots q_{s-1}$。根据归纳假设，$s-1=r-1$，即$s=r$，因此$q_{r}=p_{r}$，并且，在重新标记之后，我们可以假设$q_{i}=p_{i}, 1 \leq i \leq r-1$。这完成了归纳步骤，从而完成了定理的证明。
通常我们将自然数$n>1$唯一地写成$n=p_{1}^{n_{1}} \cdots p_{r}^{n_{r}}$，其中$p_{i}$是素数且$p_{1}<\cdots<p_{r}$，而$n_{i}$是正整数。
正如承诺的那样，我们描述了一种计算高效的方法，用于找到两个正整数$a$和$b$的最大公约数，同时展示了如何将最大公约数写成$a$和$b$的线性组合。
从$a, b$开始。写$a=b q_{1}+r_{1}$，其中$q_{1}$和$r_{1}$是整数，$0 \leq r_{1}<b$。注意$r_{1}=a+b\left(-q_{1}\right)$是$a$和$b$的线性组合。如果$r_{1}=0$，停止，否则用$b$和$r_{1}$代替$a$和$b$重复此过程，使得$b=r_{1} q_{2}+r_{2}$，其中$0 \leq r_{2}<r_{1}$，并注意$r_{2}=b-r_{1} q_{2}=b-a q_{2}+b q_{1} q_{2}$仍然是$a$和$b$的线性组合。如果$r_{2}=0$，停止，否则再次用$r_{1}$和$r_{2}$代替$b$和$r_{1}$重复，使得$r_{1}=r_{2} q_{3}+r_{3}$，其中$0 \leq r_{3}<r_{2}$。我们可以这样继续，找到$r_{1}>r_{2}>r_{3}>\cdots>r_{k} \geq 0$，其中$r_{k-1}=r_{k} q_{k+1}+r_{k+1}$。由于$r_{i}$序列递减，并且它们都是非负整数，最终此过程必须以$r_{n}$停止，使得
$r_{n+1}=0$，因此$r_{n-1}=r_{n} q_{n+1}$。该过程如下所示：
我们声称$r_{n}$是$a$和$b$的最大公约数。事实上，我们将证明：
(i) $r_{n}$同时整除$a$和$b$；
(ii) $r_{n}$是$a$和$b$的线性组合。
(i) 由于$r_{n} \mid r_{n-1}$，方程$r_{n-2}=r_{n-1} q_{n}+r_{n}$意味着$r_{n} \mid r_{n-2}$，然后从方程$r_{k-1}=r_{k} q_{k+1}+r_{k+1}$反向推导，我们看到（通过反向归纳法）$r_{n} \mid r_{k-1}$对于所有$k<n$。事实是$b=r_{1} q_{2}+r_{2}$，并且$r_{n}$整除$r_{1}$和$r_{2}$意味着$r_{n}$整除$b$，然后方程$a=b q_{1}+r_{1}$意味着$r_{n}$也整除$a$。
(ii) 另一方面，我们已经看到$r_{1}$和$r_{2}$是$a$和$b$的线性组合。通过归纳法，如果$r_{k-1}$和$r_{k}$是$a$和$b$的线性组合，那么方程$r_{k-1}=r_{k} q_{k+1}+r_{k+1}$意味着$r_{k+1}=r_{k-1}-r_{k} q_{k+1}$也是$a$和$b$的线性组合（因为正如我们在课堂上所见，所有$a$和$b$的线性组合的集合是$\mathbb{Z}$的子群，因此在加法、减法和整数乘法下封闭）。因此$r_{n}$也是$a$和$b$的线性组合。但我们已经看到，如果$a$和$b$的线性组合同时整除$a$和$b$并且是正数，那么它等于$a$和$b$的最大公约数。所以$r_{n}$是$a$和$b$的最大公约数。
这个算法比解释起来更容易执行！例如，要找到34和38的最大公约数，我们有
这表示$2=\operatorname{gcd}(34,38)$，并且$2=34-4(8)=34-(38-34)(8)=9(34)+(-8)(38)$。
选择$q_{k+1}$和$r_{k+1}$使得$r_{k-1}=r_{k} q_{k+1} \pm r_{k+1}$，其中$r_{k+1}<r_{k}$，并且选择符号使得$r_{k+1}$尽可能小，通常更高效。换句话说，我们允许形式为$-r_{k}$的负余数，目标是使余数的绝对值最小。例如，要找到7和34的最大公约数，我们可以写
从而看出最大公约数是1，并且$1=7-6=7-(34-4(7))=-34+5(7)$，或者我们可以直接看到
一个更复杂的例子是以下内容，以找到1367和298的最大公约数：
因此最大公约数是1，稍加耐心会发现